#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// queue 表示组队方法
// 1 - 男生 0 - 女生
// helper({1})
// helper({1, 1})
// helper({1, 1, 1})
// result = 2


// helper({1, 1, 1, 1}) => 2
// result = 1 在队伍中已经有 4 个男生的情况下，再追加一个男生是一个可行的排队方法

// helper({1, 1, 1, 0}) => 1
// helper({1, 1, 1, 0, 1}) => 1


// helper({1, 1, 1, 1, 1}) => 1
// helper({1, 1, 1, 1, 0}) => 1
// result = 2 在队伍中已经有 4 个男生的情况下，可以有两种不同的排队方法
// 2178309
int helper(vector<int> queue) {
  // 终结条件
  if (queue.size() == 30) {
    return 1;
  }

  /*

  */
  int result = 0; // 结果
  vector<int> copy = queue;
  // 1. 在 copy 的队尾无条件加一个男生
  copy.push_back(1);
  result = helper(copy);

  copy = queue;
  // 2. 在 copy 的末尾有条件的情况下，追加女生
  // 只有 copy 的最后一个元素是男生的时候
  if (copy.back() == 1) {
    copy.push_back(0);
    result += helper(copy);
  }

  return result;
}

int nPlus1Feet() {
  // 11111111111111000001111111
  return helper({1}) + helper({0});
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << nPlus1Feet() << endl;
  return 0;
}
